// 给你一个列表 nums ，里面每一个元素都是一个整数列表。请你依照下面各图的规则，按顺序返回 nums 中对角线上的整数。
//
//
//
// 示例 1：
//
//
//
// 输入：nums = [[1,2,3],[4,5,6],[7,8,9]]
// 输出：[1,4,2,7,5,3,8,6,9]
//
//
// 示例 2：
//
//
//
// 输入：nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
// 输出：[1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]
//
//
// 示例 3：
//
// 输入：nums = [[1,2,3],[4],[5,6,7],[8],[9,10,11]]
// 输出：[1,4,2,5,3,8,6,9,7,10,11]
//
//
// 示例 4：
//
// 输入：nums = [[1,2,3,4,5,6]]
// 输出：[1,2,3,4,5,6]
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 10^5
// 1 <= nums[i].length <= 10^5
// 1 <= nums[i][j] <= 10^9
// nums 中最多有 10^5 个数字。
//
// Related Topics 数组 排序 堆（优先队列） 👍 65 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

// Java：对角线遍历 II
public class P1424DiagonalTraverseIi {
    public static void main(String[] args) {
        Solution solution = new P1424DiagonalTraverseIi().new Solution();
        // TO TEST
        int[][] mat = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        int[] diagonalOrder = solution.findDiagonalOrder(mat);
        System.out.println(diagonalOrder.toString());
    }
    // leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] findDiagonalOrder(List<List<Integer>> nums) {
            int[][] mat = {};
            for (int i = 0; i < nums.size(); i++) {
                //
                List<Integer> integers = nums.get(i);
                for (int j = 0; j < integers.size(); j++) {
                    mat[i][j] = integers.get(j);
                }
            }
            return this.findDiagonalOrder(mat);
        }

        public int[] findDiagonalOrder(int[][] mat) {
            int m = mat.length;
            int n = mat[0].length;
            for (int i = 0; i < m; i++) {
                if (mat[i].length > n) {
                    n = mat[i].length;
                }
            }

            int i = 0;
            List<Integer> resList = new ArrayList<>();
            while (i < m + n) {

                // 1 3 5趟
                int x1 = i < m ? i : m - 1;
                int y1 = i - x1;
                while (x1 >= 0 && y1 < n) {
                    resList.add(mat[x1][y1]);
                    x1--;
                    y1++;
                }
                i++;

                if (i >= m + n) {
                    break;
                }
            }
            int[] res = new int[resList.size()];
            for (int j = 0; j < resList.size(); j++) {
                res[j] = resList.get(j);
            }
            return res;
        }
    }
    // leetcode submit region end(Prohibit modification and deletion)

}
